package pers.vic.basics.leetcode;

/**
 * @author Vic.xu
 * @description:5. 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * @date: 2020/10/30 0030 10:27
 */
public class J0005_M_LongestPalindrome {

    /*
        4种算法

        1. 写个没有暴力循环的效率为O(N^3)的  倒也问题不大

        2. 中心扩散：勉强可以写下
           2.1 以每个字符串为中心，向两边计算是否是回文
           2.2 偶数情况下，字符串和字符串的右侧一起作为中心向两边扩散

        3.动态规划，之前写背包问题的时候  用递归写过   ，暂时不会动态规划算法，希望后面有时间学习学习

        4. Manacher 算法  不会
    */


    //中心扩散
    public static String longestPalindrome(String s) {
        //前置判断省略
        int len = s.length();
        //当前回文串的起始位置 和 最大长度
        int start = 0;
        int max = 1;
        for (int i = 0; i < len-1; i++) {
            //以i下标为中心，向两边扩散，获得最大回文串的长度
            int max1 = getPalindromeMax(s, i, i);
            //以i下标和i下标的右侧为中心，向两边扩散，获得最大回文串长度
            int max2 = getPalindromeMax(s, i, i + 1);
            int curMax = max1 > max2 ? max1 : max2;
            if (curMax > max) {
                max = curMax;
                //计算当前回文的起始位置：
                start = i - (max + 1) / 2 + 1;
            }
        }

        return s.substring(start, start + max);
    }

    private static int getPalindromeMax(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {

            left--;
            right++;
        }
        return right - left - 1;
    }

    // 先来个暴力解决的，遍历每个大于2子字符串是否是回文
    public static String longestPalindrome2(String s) {
        int len = s.length();
        String res = String.valueOf(s.charAt(0));
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 2; j < len + 1; j++) {
                String sub = s.substring(i, j);
                if (isPalindrome(sub) && sub.length() > res.length()) {
                    res = sub;
                }
            }
        }
        return res;
    }

    //是否是回文，s长度大于等2
    public static boolean isPalindrome(String s) {
        int len = s.length();
        if (len == 1) {
            return true;
        }
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
        s = "ccc";
        System.out.println(longestPalindrome(s));
    }
}
